package 二叉树;

/**
 * @ClassName : _111_二叉树的最小深度_lc评论区
 * @Author : 骆发茂
 * @Date: 2021/12/11 18:49
 * @Description : https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/li-jie-zhe-dao-ti-de-jie-shu-tiao-jian-by-user7208/
 */
public class _111_二叉树的最小深度_lc评论区 {
//    思路：
//    很多人写出的代码都不符合 1,2 这个测试用例，是因为没搞清楚题意
//
//    题目中说明:叶子节点是指没有子节点的节点，这句话的意思是 1 不是叶子节点
//
//    题目问的是到叶子节点的最短距离，所以所有返回结果为 1 当然不是这个结果
//
//            另外这道题的关键是搞清楚递归结束条件
//
//    叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点
//    当 root 节点左右孩子都为空时，返回 1
//    当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度
//    当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值
//    第一版代码:


    /*每个节点都是基本三种情况，没有子节点、一个子结点、两个子节点，递归写法*/
    class Solution {
        public int minDepth(TreeNode root) {
            if(root == null) return 0;
            //这道题递归条件里分为三种情况
            //1.左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可
            if(root.left == null && root.right == null) return 1;
            //2.如果左孩子和由孩子其中一个为空，那么需要返回比较大的那个孩子的深度
            int m1 = minDepth(root.left);
            int m2 = minDepth(root.right);
            //这里其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1;
            //也就是m1,m2其中有一个可能是0，就是m1可能是0，m2可能是0，不知道哪个，所以就m1+m2+1；其中一个是0的
            //+1是因为本身的层，子层+1 == 现在所处的层
            if(root.left == null || root.right == null) return m1 + m2 + 1;

            //3.最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可
            return Math.min(m1,m2) + 1;
        }
    }
//    代码可以进行简化，当左右孩子为空时 m1m1 和 m2m2 都为 00
//
//    可以和情况 22 进行合并，即返回 m1+m2+1m1+m2+1
//
//    简化后代码如下:


    class Solution2 {
        public int minDepth(TreeNode root) {
            if(root == null) return 0;
            int m1 = minDepth(root.left);
            int m2 = minDepth(root.right);
            //1.如果左孩子和右孩子有为空的情况，直接返回m1+m2+1
            //2.如果都不为空，返回较小深度+1
            return root.left == null || root.right == null ? m1 + m2 + 1 : Math.min(m1,m2) + 1;
        }
    }


    class Solution3 {
        public int minDepth(TreeNode root) {
            if (root == null) return 0;
            else if (root.left == null) {
                return minDepth(root.right) + 1;
            } else if (root.right == null) {
                return minDepth(root.left) + 1;
            } else{
                return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
            }
        }
    }

}